package com.Dec_Forteen;

/**
 * 968. 监控二叉树
 * 给定一个二叉树，我们在树的节点上安装摄像头。
 *
 * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
 *
 * 计算监控树的所有节点所需的最小摄像头数量。
 *
 *
 *
 * 2022/11/14 19:46
 */

public class Solution968 {

    /**
     * 使用贪心算法
     * 2：表示当前是覆盖状态（即有相机）
     * 1：表示本节点有相机
     * 0：表示本节点没有覆盖（需要放相机）
     */
    int res=0;

    public int minCameraCover(TreeNode root) {
        if (minCamera(root)==0) res++;
        return res;
    }

    public int minCamera(TreeNode root){
        if (root==null) return 2;
        int left=minCamera(root.left);
        int right=minCamera(root.right);
        if (left==2&&right==2){
            return 0;
        }else if (left==0||right==0){
            res++;
            return 1;
        }else {
            return 2;
        }
    }

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

}
